package class10;

import common.DoubleList;
import common.DoubleListNode;
import common.ListNodeUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/lru-cache/
 * 设计 LRU 缓存(最近最少访问)
 * 缓存大小为3，
 * 1. [字符，访问次数]: [a,3],[b,9],[c,15] 在缓存中
 * 2. 当 [d,2] 过来时淘汰 [a,3],将 [a,3] 淘汰，因为 a 只被访问了 3 次
 * 3. 缓存变成：[b,9],[c,15],[d,2]
 * 4. 当 [e,5] 进来时，最近最少访问的是 b,因此被淘汰。而 [d,2]是刚进来不是最远的
 * 双向链表实现
 */
public class Code09_LRU_DoubleList {
    public static void main(String[] args) {
//        DoubleList doubleList = new DoubleList();
//        DoubleListNode t = new DoubleListNode(3);
//        doubleList.addNode(new DoubleListNode(1));
//        doubleList.addNode(new DoubleListNode(2));
//        doubleList.addNode(t);
//        doubleList.addNode(new DoubleListNode(4));
//        doubleList.addNode(new DoubleListNode(5));
//        System.out.println("doubleList = " + doubleList);
//        doubleList.moveNodeToTail(t);
//        System.out.println("doubleList = " + doubleList);

        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        System.out.println("lruCache.nodeList = " + lruCache.nodeList);
        lruCache.put(3,3);
        lruCache.put(6,6);
        System.out.println("lruCache.nodeList = " + lruCache.nodeList);

    }

    /**
     * 双向链表实现
     */
    private static class LRUCache {
        private Map<Integer, DoubleListNode> keyNodesMap;

        private DoubleList nodeList;

        private final int capacity;

        private LRUCache(int cap) {
            keyNodesMap = new HashMap<>();
            nodeList = new DoubleList();
            capacity = cap;
        }

        public int get(int k) {
            if (keyNodesMap.containsKey(k)) {
                DoubleListNode node = keyNodesMap.get(k);
                nodeList.moveNodeToTail(node);
                return node.val;
            }
            return -1;
        }

        public void put(int k, int v) {
            if (keyNodesMap.containsKey(k)) {
                DoubleListNode node = keyNodesMap.get(k);
                node.val = v;
                nodeList.moveNodeToTail(node);
            } else {
                if (capacity == keyNodesMap.size()) {
                    keyNodesMap.remove(nodeList.remveHead().key);
                }
                DoubleListNode node = new DoubleListNode(k, v);
                keyNodesMap.put(k, node);
                nodeList.addNode(node);
            }
        }
    }
}

